package solution.Title_1_10;

import java.util.HashMap;
import java.util.Map;

/**
 * @author FreyaZ
 * @version 2018-01-01

    1.
    Given an array of integers, return indices of the two numbers such that they add up to a specific target.
    You may assume that each input would have exactly one solution, and you may not use the same element twice.

    Example:
    Given nums = [2, 7, 11, 15], target = 9,

    Because nums[0] + nums[1] = 2 + 7 = 9,
    return [0, 1].

 */
public class TwoSum {

    public static int[] twoSum(int[] nums, int target) {
        // 方法一：循环 list，时间复杂度：O(n²)

        // 方法二：通过二分法等进行循环，时间复杂度：(O(n), O(n²)]

        // 方法三：使用 hashMap: 数组中的值作为 key，index 作为 value
        Map<Integer, Integer> numMap = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            numMap.put(nums[i], i);
        }

        /*
        循环原有数组，因为数组中可能会有重复值
        有一个小前提：因为预设了只有一个 solution，所以不会有超过两个的重复值
        如果有重复值，在 numMap 中存储的 value，是后一个重复值的 index
         */
        for (int i = 0; i < nums.length; i++) {
            int otherNum = target - nums[i];
            if (numMap.containsKey(otherNum) && i != numMap.get(otherNum)) {
                return new int[] {i, numMap.get(otherNum)};
            }
        }

        return null;
    }

}
